package com.sakura.二分查找;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Code05_区间内查询数字的频率 {

    public static void main(String[] args) {
        RangeFreqQuery rangeFreqQuery = new RangeFreqQuery(new int[]{12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56});
        System.out.println(rangeFreqQuery.query(1, 2, 4));
    }
}

class RangeFreqQuery {
    // 记录arr中每个数字出现的位置
    private HashMap<Integer, List<Integer>> map = new HashMap<>();
    public RangeFreqQuery(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            map.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int query(int left, int right, int value) {
        List<Integer> v = map.get(value);
        if (v == null) return 0;

        // 找到的一个大于 left的位置
        int l = lowerBound(v, left);
        // 找到对一个大于 right的位置
        int r = lowerBound(v, right + 1);

        return r - l;
    }

    private int lowerBound(List<Integer> list, int target) {
        int left = -1;
        int right = list.size();
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return right;
    }
}